package algorithm.leetcode;

import java.util.*;

public class TopKFrequent {

    public List<String> topKFrequent(String[] words, int k) {
        //优先级队列
        Map<String, Integer> map = new HashMap<>();
        for(int i=0; i<words.length; i++) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }

        PriorityQueue<Map.Entry<String, Integer>> pqueue = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>(){
            public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2) {
                return entry1.getValue().equals(entry2.getValue()) ? entry2.getKey().compareTo(entry1.getKey()) :
                        entry1.getValue() - entry2.getValue();
            }
        });

        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            pqueue.offer(entry);
            if(pqueue.size() > k) {
                pqueue.poll();
            }
        }

        List<String> list = new ArrayList<>();
        while(!pqueue.isEmpty()) {
            list.add(pqueue.poll().getKey());
        }

        Collections.reverse(list);

        return list;

    }

    public static void main(String[] args) {
        List<String> result = new TopKFrequent().topKFrequent(new String[]{"i","love","leetcode","i","love","coding"}, 3);
        result.stream().forEach(item ->{
            System.out.println(item + " ");
        });
    }
}
